﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Chapter_9__Recursion_
{
    public static class Ex_9_1
    {
        static bool UseDynamicProgramming = true;

        public static long GetPossibleWays(int NumSteps)
        {
            long[] map = new long[NumSteps + 1];

            DateTime start = DateTime.Now;
            long result = GetPossibleWaysRecursive(NumSteps, map);
            TimeSpan elapsedTime = DateTime.Now - start;
            double milliseconds = elapsedTime.TotalMilliseconds;

            return result;
        }

        static long GetPossibleWaysRecursive(int NumSteps, long[] map)
        {
            long NumWays = 0;
            if (NumSteps == 0)
                return 1;
            else if (NumSteps < 0)
                return 0;
            else if (UseDynamicProgramming && map[NumSteps] > 0)
                return map[NumSteps];

            NumWays += GetPossibleWaysRecursive(NumSteps - 1, map);
            NumWays += GetPossibleWaysRecursive(NumSteps - 2, map);
            NumWays += GetPossibleWaysRecursive(NumSteps - 3, map);

            map[NumSteps] = NumWays;

            return NumWays;
        }
    }
}
